package imooc_math.sort;

import java.util.Arrays;

import javax.swing.plaf.synth.SynthSpinnerUI;

import resource.SortTestHelper;
//插入排序
//在有序的情况下可以变成O(n)的算法
public class InsertionSort {
	 // 对arr[l...r]的区间使用InsertionSort排序*********copy**************
    public static void sort(Comparable[] arr, int l, int r){

        for( int i = l + 1 ; i <= r ; i ++ ){
            Comparable e = arr[i];
            int j = i;
            for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }
	public static Object[] sort(Comparable[] arry){	
		/*int n=arry.length;
		for(int i=1;i<n;i++){
			//拿第i个值与第i-1个的值相比，后者小的话交换位置，继续将i-1与i-2相比...,直到后者大于前者为止
			//每个内循环有停止条件
			for(int j=i;j>0&&arry[j].compareTo(arry[j-1])<0;j--){
				swap(arry,j,j-1);//交换比比较更加耗时，这也是初代的插入排序比选择排序耗费更多时间的原因
			}
		}
		return arry;*/
		int n=arry.length;
		for(int i=1;i<n;i++){
			int j;
			Comparable e=arry[i];
			//拿第i个值与第i-1个的值相比，后者小的话交换位置，继续将i-1与i-2相比...,直到后者大于前者为止
			//每个内循环有停止条件
			for(j=i;j>0&& e.compareTo(arry[j-1])<0;j--){
				//swap(arry,j,j-1);//交换比比较更加耗时，这也是初代的插入排序比选择排序耗费更多时间的原因
				arry[j]=arry[j-1];
			}
			arry[j]=e;
		}
		return arry;
	}
/*	public static void sort(Comparable[] arr){
		int n = arr.length;
        for (int i = 0; i < n; i++) {

            // 寻找元素arr[i]合适的插入位置

            // 写法1
//            for( int j = i ; j > 0 ; j -- )
//                if( arr[j].compareTo( arr[j-1] ) < 0 )
//                    swap( arr, j , j-1 );
//                else
//                    break;

            // 写法2
//            for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
//                swap(arr, j, j-1);

            // 写法3
            Comparable e = arr[i];
            int j = i;
            for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;

        }
    }*/
	public static void swap(Object [] arr,int a,int b){
		Object t=arr[a];
		arr[a]=arr[b];
		arr[b]=t;
	}
	public static void main(String[] args) {
		/*Integer[] arry=new  SortTestHelper().generateRandomArray(10, 0, 20);
		Integer[] result=sort(arry);
		new  SortTestHelper().printArray(result);*/
		
		/*Integer[] arry=new  SortTestHelper().generateRandomArray(20000, 0, 3);
		Integer[] arry2=new  SortTestHelper().generateRandomArray(20000, 0, 3);
		//System.out.println(arry);
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		SortTestHelper sth=new SortTestHelper();
		sth.testSort("imooc_math.SelectionSort", arry);
		sth.testSort("imooc_math.InsertionSort", arryCopy);*/
		
		Integer[] arry=new  SortTestHelper().generateNearlyOrderedArray(50000,10);
		SortTestHelper sth=new SortTestHelper();
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		sth.testSort("imooc_math.InsertionSort", arryCopy);
		sth.testSort("imooc_math.SelectionSort", arry);
		
		
		
		
	}
}
